package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.util.TreeNode;

/**
 * [探索字节跳动 - 力扣 (LeetCode)](https://leetcode.cn/explore/featured/card/bytedance/244/linked-list-and-tree/1026/)
 *
 * @author 60906
 * @date 2021/5/6 14:15
 */
public class Q_二叉树的最近公共祖先 {


    class Solution {

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return func(root, p, q).res;
        }

        Info func(TreeNode x, TreeNode p, TreeNode q) {
            if (x == null) {
                return new Info(null, false, false);
            }
            Info leftInfo = func(x.left, p, q);
            Info rightInfo = func(x.right, p, q);

            TreeNode res = leftInfo.res != null ? leftInfo.res : rightInfo.res;

            boolean hasP = leftInfo.hasP || rightInfo.hasP || x == p;
            boolean hasQ = leftInfo.hasQ || rightInfo.hasQ || x == q;

            if (res == null) {
                res = hasP && hasQ ? x : res;
            }

            return new Info(res, hasP, hasQ);
        }


        // 1) 已经有结果，一边
        // 2）两边，自己是结果
        // 3）有其一
        class Info {
            TreeNode res;
            boolean hasP;
            boolean hasQ;

            public Info(TreeNode res, boolean hasP, boolean hasQ) {
                this.res = res;
                this.hasP = hasP;
                this.hasQ = hasQ;
            }
        }


    }



    private class Solution1 {

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return func(root, p, q).ans;
        }

        // (1) ans; (2) 只有p; (3) 只有q; (4) 都没有
        private Info func(TreeNode root, TreeNode p, TreeNode q) {
            Info info = new Info();
            if (root == null) {
                return info;
            }
            Info leftInfo = func(root.left, p, q);
            if (leftInfo.ans != null) {
                return leftInfo;
            }
            Info rightInfo = func(root.right, p, q);
            if (rightInfo.ans != null) {
                return rightInfo;
            }
            TreeNode ansp = leftInfo.p != null ? leftInfo.p : rightInfo.p;
            TreeNode ansq = leftInfo.q != null ? leftInfo.q : rightInfo.q;
            Info myInfo = new Info();
            if (ansp == null && ansq == null) {
                if (root == p) {
                    myInfo.p = root;
                } else if (root == q) {
                    myInfo.q = root;
                }
            } else if (ansp == null) {
                myInfo.q = ansq;
                myInfo.p = root == p ? root : null;
            } else if (ansq == null) {
                myInfo.p = ansp;
                myInfo.q = root == q ? root : null;
            } else {
                myInfo.p = ansp;
                myInfo.q = ansq;
                myInfo.ans = root;
            }

            return myInfo;
        }

        class Info {
            TreeNode ans;
            TreeNode p;
            TreeNode q;

            public Info() {
            }

            public Info(TreeNode ans, TreeNode p, TreeNode q) {
                this.ans = ans;
                this.p = p;
                this.q = q;
            }
        }

    }

}
